一.定义
若能将无向图 画在平面上使得任意两条无重合顶点的边不相交，则称 是平面图。
在平面图中，由边构成的最小区域称为面，包围该面的边数记为该面的度，特殊的，平面图外的区域也为一个面。
比如图一不是平面图，图二因为和图三等价，是平面图。
二.性质
-
平面图的面的度的和等于边数的两倍
显然。 -
欧拉公式：对于联通平面图，， 其中 为点数 ， 为边数 ， 为面数
证明：
当 ，因为图联通，所以 ，成立。
对 进行数学归纳，若 成立，那么对于第 条边
- 两端均为连通块的点，那么便会增加一个面，点数不变。
- 一端为连通块的点，另一端为不在连通块内的点，那么会增加一个点，面数不变。
所以结论成立。
推论：对于任意平面图， ， 为平面图的连通块个数
当 ，那么 , 成立。
对 进行数学归纳，若 成立，那么对于第 条边
- 两端的点属于一个连通块，那么便会增加一个面。
- 两端的点不属于一个连通块，那么便会减少一个连通块。
所以结论成立。
3.当 ，平面图的边数不大于 。
一个面至少有三条边，那么平面图的面的度的和至少为 。
又由 得平面图的面的度的和为 。
所以 ：
代入欧拉公式得：
三.例题
1.P3209 [HNOI2010]平面图判定
